"""
Ambients of elements with Fourier expansion and partially known relations.

AUTHOR :
    -- Martin Raum (2010 - 03 - 10) Initial version
"""

#===============================================================================
# 
# Copyright (C) 2010 Martin Raum
# 
# This program is free software; you can redistribute it and/or
# modify it under the terms of the GNU General Public License
# as published by the Free Software Foundation; either version 3
# of the License, or (at your option) any later version.
# 
# This program is distributed in the hope that it will be useful, 
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
# General Public License for more details.
# 
# You should have received a copy of the GNU General Public License
# along with this program; if not, see <http://www.gnu.org/licenses/>.
#
#===============================================================================

from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_functor import \
            GradedExpansionFunctor, GradedExpansionEvaluationHomomorphism
from operator import xor
from sage.misc.cachefunc import cached_method
from sage.misc.flatten import flatten
from sage.misc.misc import prod
from sage.rings.all import Integer
from sage.structure.element import Element
from sage.structure.parent import Parent
from sage.structure.sequence import Sequence

## late import in GradedExpansionAmbient_abstract
GradedExpansionSubmodule = None 
GradedExpansionSubmodule_abstract = None

#===============================================================================
# GradedExpansionAmbient_abstract
#===============================================================================

class GradedExpansionAmbient_abstract :
    """
    A ring of graded expansions. This is a polynomial ring with relations
    and a mapping to an (equivariant) monoid power series. These should
    respect the given relations, but there can me more relations of the
    Fourier expansions that are stored for the polynomial ring.
    """
    
    def __init__ ( self, base_ring_generators, generators, relations,
                   grading, all_relations = True, reduce_before_evaluating = True) :
        """
        INPUT:
            - ``base_ring_generators``      -- A sequence of (equivariant) monoid power series with
                                               coefficient domain the base ring of the coefficient
                                               domain of the generators or ``None``.
            - ``generators``                -- A sequence of (equivariant) monoid power series; The generators
                                               of the ambient over the ring generated by the base ring
                                               generators.
            - ``relations``                 -- An ideal in a polynomial ring with ``len(base_ring_generators) + len(generators)``
                                               variables.
            - ``grading``                   -- A grading deriving from :class:~`fourier_expansion_framework.gradedexpansions.gradedexpansion_grading`;
                                               A grading for the polynomial ring of the relations.
            - ``all_relations``             -- A boolean (default: ``True``); If ``True`` the relations given
                                               for the polynomial ring are all relations that the Fourier
                                               expansion have.
            - ``reduce_before_evaluating``  -- A boolean (default: ``True``); If ``True`` any monomial
                                               will be Groebner reduced before the Fourier expansion
                                               is calculated.
        
        NOTE:
            The grading must respect the relations of the generators.
        
        EXAMPLES::
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_basicmonoids import *
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_ring import *
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_element import *
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_grading import DegreeGrading
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_ring import *
            sage: mps = MonoidPowerSeriesRing(QQ, NNMonoid(False))
            sage: ger = GradedExpansionRing_class(None, Sequence([mps(1)]), PolynomialRing(ZZ, 'a').ideal(0), DegreeGrading((1,))) # indirect doctest
            sage: ger = GradedExpansionRing_class(Sequence([MonoidPowerSeries(mps, {1 : 1}, mps.monoid().filter(2))]), Sequence([MonoidPowerSeries(mps, {1 : 1, 2 : 3}, mps.monoid().filter(4))]), PolynomialRing(ZZ, ['a', 'b']).ideal(0), DegreeGrading((1,2))) # indirect doctest
            sage: ger = GradedExpansionRing_class(Sequence([MonoidPowerSeries(mps, {1 : 1}, mps.monoid().filter(2))]), Sequence([MonoidPowerSeries(mps, {1 : 1, 2 : 3}, mps.monoid().filter(4))]), PolynomialRing(ZZ, ['a', 'b']).ideal(0), DegreeGrading((1,2)), all_relations = False) # indirect doctest
            sage: ger = GradedExpansionRing_class(Sequence([MonoidPowerSeries(mps, {1 : 1}, mps.monoid().filter(2))]), Sequence([MonoidPowerSeries(mps, {1 : 1, 2 : 3}, mps.monoid().filter(4))]), PolynomialRing(ZZ, ['a', 'b']).ideal(0), DegreeGrading((1,2)), reduce_before_evaluating = False) # indirect doctest
        """
        global GradedExpansionSubmodule, GradedExpansionSubmodule_abstract
        from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_submodule import GradedExpansionSubmodule
        from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_submodule import GradedExpansionSubmodule_abstract

        self.__relations = relations
        self.__all_relations = all_relations
        self.__grading = grading
        
        if base_ring_generators is None :
            base_ring_generators = Sequence([], universe = generators.universe().base_ring())
        self.__base_gens = \
          tuple([ self.base_ring()._element_class( self.base_ring(), self.base_ring().relations().ring()(g) )
                  for g in self.__relations.ring().gens()[:len(base_ring_generators)]])
        self.__gens = \
         tuple([ self._element_class( self, g )
                 for g in self.__relations.ring().gens()[len(base_ring_generators):] ])

        # We expect the base ring generators to either admit coercion
        # into the universe of the generators or to act on it from the left 
        self.__base_gen_expansions = base_ring_generators
        self.__gen_expansions = generators
        self.__evaluation_hom = GradedExpansionEvaluationHomomorphism( self.__relations, self.__base_gen_expansions,
                                                                       self.__gen_expansions, self.__gen_expansions.universe(),
                                                                       reduce_before_evaluating )

        self.__graded_submodules = dict()
    
    def ngens(self) :
        """
        The number of generators of ``self`` over the base expansion ring.
        
        OUTPUT:
            An integer.
        
        EXAMPLES::
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_basicmonoids import *
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_ring import *
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_element import *
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_grading import DegreeGrading
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_ring import *
            sage: mps = MonoidPowerSeriesRing(QQ, NNMonoid(False))
            sage: ger = GradedExpansionRing_class(None, Sequence([mps(1)]), PolynomialRing(ZZ, 'a').ideal(0), DegreeGrading((1,)))
            sage: ger.ngens()
            1
        """
        return len(self.__gens)
    
    def gen(self, i = 0) :
        """
        The `i`-th generator of ``self`` over the base expansion ring.

        INPUT:
            - `i` -- An integer.
        
        OUTPUT:
            An instance of :class:~`fourier_expansion_framework.gradedexpansions.gradedexpansion_element.GradedExpansion_abstract`.

        EXAMPLES::
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_basicmonoids import *
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_ring import *
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_element import *
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_grading import DegreeGrading
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_ring import *
            sage: mps = MonoidPowerSeriesRing(QQ, NNMonoid(False))
            sage: ger = GradedExpansionRing_class(None, Sequence([mps(1)]), PolynomialRing(ZZ, 'a').ideal(0), DegreeGrading((1,)))
            sage: ger.gen(0)
            Graded expansion a
        """
        return self.__gens[i]
    
    def gens(self) :
        """
        The generators of ``self`` over the base expansion ring.
        
        OUTPUT:
            A tuple of instances of :class:~`fourier_expansion_framework.gradedexpansions.gradedexpansion_element.GradedExpansion_abstract`.

        EXAMPLES::
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_basicmonoids import *
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_ring import *
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_element import *
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_grading import DegreeGrading
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_ring import *
            sage: mps = MonoidPowerSeriesRing(QQ, NNMonoid(False))
            sage: ger = GradedExpansionRing_class(None, Sequence([mps(1)]), PolynomialRing(ZZ, 'a').ideal(0), DegreeGrading((1,)))
            sage: ger.gens()
            (Graded expansion a,)
        """
        return self.__gens
    
    def nbasegens(self) :
        """
        Number of generators of the base expansion ring.
        
        OUTPUT:
            An integer.
        
        TESTS::
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_basicmonoids import *
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_ring import *
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_element import *
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_grading import DegreeGrading
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_ring import *
            sage: mps = MonoidPowerSeriesRing(QQ, NNMonoid(False))
            sage: ger = GradedExpansionRing_class(None, Sequence([mps(1)]), PolynomialRing(ZZ, 'a').ideal(0), DegreeGrading((1,)))
            sage: ger.nbasegens()
            0
            sage: ger = GradedExpansionRing_class(Sequence([MonoidPowerSeries(mps, {1 : 1}, mps.monoid().filter(2))]), Sequence([MonoidPowerSeries(mps, {1 : 1, 2 : 3}, mps.monoid().filter(4))]), PolynomialRing(ZZ, ['a', 'b']).ideal(0), DegreeGrading((1,2)))
            sage: ger.nbasegens()
            1
        """
        return len(self.__base_gens)
    
    def basegen(self, i) :
        """
        The `i`-th generator of the base expansion ring.
        
        INPUT:
            - `i` -- An integer.
            
        OUTPUT:
            An instance of :class:~`fourier_expansion_framework.gradedexpansions.gradedexpansion_element.GradedExpansion_abstract`.
        
        TESTS::
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_basicmonoids import *
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_ring import *
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_element import *
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_grading import DegreeGrading
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_ring import *
            sage: mps = MonoidPowerSeriesRing(QQ, NNMonoid(False))
            sage: ger = GradedExpansionRing_class(None, Sequence([mps(1)]), PolynomialRing(ZZ, 'a').ideal(0), DegreeGrading((1,)))
            sage: ger = GradedExpansionRing_class(Sequence([MonoidPowerSeries(mps, {1 : 1}, mps.monoid().filter(2))]), Sequence([MonoidPowerSeries(mps, {1 : 1, 2 : 3}, mps.monoid().filter(4))]), PolynomialRing(ZZ, ['a', 'b']).ideal(0), DegreeGrading((1,2)))
            sage: ger.basegen(0)
            Graded expansion a
        """
        return self.__base_gens[i]
    
    def basegens(self) :
        """
        The generators of the base expansion ring.
        
        OUTPUT:
            A tuple of instances of :class:~`fourier_expansion_framework.gradedexpansions.gradedexpansion_element.GradedExpansion_abstract`.
        
        TESTS::
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_basicmonoids import *
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_ring import *
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_element import *
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_grading import DegreeGrading
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_ring import *
            sage: mps = MonoidPowerSeriesRing(QQ, NNMonoid(False))
            sage: ger = GradedExpansionRing_class(Sequence([MonoidPowerSeries(mps, {1 : 1}, mps.monoid().filter(2))]), Sequence([MonoidPowerSeries(mps, {1 : 1, 2 : 3}, mps.monoid().filter(4))]), PolynomialRing(ZZ, ['a', 'b']).ideal(0), DegreeGrading((1,2)))
            sage: ger.basegens()
            (Graded expansion a,)
        """
        return self.__base_gens
    
    def is_field(self) :
        """
        OUTPUT:
            A boolean.
        
        TESTS::
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_basicmonoids import *
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_ring import *
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_element import *
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_grading import DegreeGrading
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_ring import *
            sage: mps = MonoidPowerSeriesRing(QQ, NNMonoid(False))
            sage: ger = GradedExpansionRing_class(None, Sequence([mps(1)]), PolynomialRing(ZZ, 'a').ideal(0), DegreeGrading((1,)))
            sage: ger.is_field()
            False
        """
        ## Never delete this. It is called during intialisation of deriving classes
        ## over number fields and and causes coercion to fail. 
        return False
    
    def grading(self) :
        """
        The grading imposed on this ring.
        
        OUTPUT:
            An isntance of :class:~`fourier_expansion_framework.gradedexpansions.gradedexpansion_grading`.

        EXAMPLES::
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_basicmonoids import *
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_ring import *
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_element import *
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_grading import DegreeGrading
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_ring import *
            sage: mps = MonoidPowerSeriesRing(QQ, NNMonoid(False))
            sage: ger = GradedExpansionRing_class(Sequence([MonoidPowerSeries(mps, {1 : 1}, mps.monoid().filter(2))]), Sequence([MonoidPowerSeries(mps, {1 : 1, 2 : 3}, mps.monoid().filter(4))]), PolynomialRing(ZZ, ['a', 'b']).ideal(0), DegreeGrading((1,2)))
            sage: ger.grading() == DegreeGrading((1,2))
            True
        """
        return self.__grading
    
    def relations(self) :
        """
        The relation of the generators of this ring with in the underlying
        polynomial ring.
        
        OUTPUT:
            An ideal in a polynomial ring.
        
        SEE:
            all_relations_known
        
        TESTS::
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_basicmonoids import *
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_ring import *
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_element import *
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_grading import DegreeGrading
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_ring import *
            sage: mps = MonoidPowerSeriesRing(QQ, NNMonoid(False))
            sage: ger = GradedExpansionRing_class(None, Sequence([mps(1)]), PolynomialRing(ZZ, 'a').ideal(0), DegreeGrading((1,)))
            sage: ger.relations()
            Principal ideal (0) of Univariate Polynomial Ring in a over Integer Ring
            sage: P.<a,b,c> = PolynomialRing(ZZ)
            sage: ger = GradedExpansionRing_class(Sequence([MonoidPowerSeries(mps, {1 : 1}, mps.monoid().filter(2))]), Sequence([MonoidPowerSeries(mps, {1 : 1, 2 : 3}, mps.monoid().filter(4))]), P.ideal(a*b - c), DegreeGrading((1,2)))
            sage: ger.relations()
            Ideal (a*b - c) of Multivariate Polynomial Ring in a, b, c over Integer Ring
        """
        return self.__relations
    
    def all_relations_known(self) :
        """
        If ``True`` is returned any relation of the Fourier expansions associated
        with elements of this ring - thought of as expansions with
        infinite precision - implies that the relation is also contained
        in ``self.relations()``.
        
        OUTPUT:
            A boolean.
        
        TESTS::
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_basicmonoids import *
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_ring import *
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_element import *
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_grading import DegreeGrading
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_ring import *
            sage: mps = MonoidPowerSeriesRing(QQ, NNMonoid(False))
            sage: ger = GradedExpansionRing_class(None, Sequence([mps(1)]), PolynomialRing(ZZ, 'a').ideal(0), DegreeGrading((1,)))
            sage: ger.all_relations_known()
            True
            sage: ger = GradedExpansionRing_class(Sequence([MonoidPowerSeries(mps, {1 : 1}, mps.monoid().filter(2))]), Sequence([MonoidPowerSeries(mps, {1 : 1, 2 : 3}, mps.monoid().filter(4))]), PolynomialRing(ZZ, ['a', 'b']).ideal(0), DegreeGrading((1,2)), all_relations = False)
            sage: ger.all_relations_known()
            False
        """
        return self.__all_relations
    
    def has_relation_free_generators(self) :
        """
        If ``True`` is returned, there are no relations of the Fourier
        expansions - thought of as expansions with infinite precision.
        
        OUTPUT:
            A boolean.
            
        TESTS::
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_basicmonoids import *
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_ring import *
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_element import *
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_grading import DegreeGrading
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_ring import *
            sage: mps = MonoidPowerSeriesRing(QQ, NNMonoid(False))
            sage: ger = GradedExpansionRing_class(None, Sequence([mps(1)]), PolynomialRing(ZZ, 'a').ideal(0), DegreeGrading((1,))) # indirect doctest
            sage: ger.has_relation_free_generators()
            True
            sage: ger = GradedExpansionRing_class(Sequence([MonoidPowerSeries(mps, {1 : 1}, mps.monoid().filter(2))]), Sequence([MonoidPowerSeries(mps, {1 : 1, 2 : 3}, mps.monoid().filter(4))]), PolynomialRing(ZZ, ['a', 'b']).ideal(0), DegreeGrading((1,2)), all_relations = False)
            sage: ger.has_relation_free_generators()
            False
            sage: P.<a,b,c> = PolynomialRing(ZZ)
            sage: ger = GradedExpansionRing_class(Sequence([MonoidPowerSeries(mps, {1 : 1}, mps.monoid().filter(2))]), Sequence([MonoidPowerSeries(mps, {1 : 1, 2 : 3}, mps.monoid().filter(4))]), P.ideal(a*b - c), DegreeGrading((1,2)))
            sage: ger.has_relation_free_generators()
            False
        """
        return self.__all_relations and self.__relations.is_zero()
    
    def _generator_expansions(self) :
        """
        The generators' Fourier expansion within a common parent.
        
        OUTPUT:
            A sequence of of (equivariant) monoid power series.
        
        TESTS::
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_basicmonoids import *
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_ring import *
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_element import *
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_grading import DegreeGrading
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_ring import *
            sage: mps = MonoidPowerSeriesRing(QQ, NNMonoid(False))
            sage: ger = GradedExpansionRing_class(None, Sequence([mps(1)]), PolynomialRing(ZZ, 'a').ideal(0), DegreeGrading((1,)))
            sage: ger._generator_expansions().universe()
            Ring of monoid power series over NN
            sage: ger._generator_expansions()[0].coefficients()
            {0: 1}
        """
        return self.__gen_expansions
    
    def _base_generator_expansions(self) :
        """
        The Fourier expansions of the generators of the base expansion ring.
        
        OUTPUT:
            A sequence of of (equivariant) monoid power series.
        
        TESTS::
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_basicmonoids import *
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_ring import *
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_element import *
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_grading import DegreeGrading
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_ring import *
            sage: mps = MonoidPowerSeriesRing(QQ, NNMonoid(False))
            sage: ger = GradedExpansionRing_class(None, Sequence([mps(1)]), PolynomialRing(ZZ, 'a').ideal(0), DegreeGrading((1,)))
            sage: ger._base_generator_expansions().universe()
            Rational Field
            sage: ger = GradedExpansionRing_class(Sequence([MonoidPowerSeries(mps, {1 : 1}, mps.monoid().filter(2))]), Sequence([MonoidPowerSeries(mps, {1 : 1, 2 : 3}, mps.monoid().filter(4))]), PolynomialRing(ZZ, ['a', 'b']).ideal(0), DegreeGrading((1,2)))
            sage: ger._base_generator_expansions()
            [Monoid power series in Ring of monoid power series over NN]
        """
        return self.__base_gen_expansions
    
    @cached_method
    def fourier_expansion_precision(self) :
        """
        A precision which is obtained by all expansions of any element.
        
        OUTPUT:
            A filter for the Fourier expansion ambient's monoid or action.
        
        TESTS::
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_basicmonoids import *
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_ring import *
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_element import *
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_grading import DegreeGrading
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_ring import *
            sage: mps = MonoidPowerSeriesRing(QQ, NNMonoid(False))
            sage: ger = GradedExpansionRing_class(None, Sequence([mps(1)]), PolynomialRing(ZZ, 'a').ideal(0), DegreeGrading((1,)))
            sage: ger.fourier_expansion_precision()
            Filtered NN up to +Infinity
            sage: ger = GradedExpansionRing_class(Sequence([MonoidPowerSeries(mps, {1 : 1}, mps.monoid().filter(2))]), Sequence([MonoidPowerSeries(mps, {1 : 1, 2 : 3}, mps.monoid().filter(4))]), PolynomialRing(ZZ, ['a', 'b']).ideal(0), DegreeGrading((1,2)))
            sage: ger.fourier_expansion_precision()
            Filtered NN up to 2
        """
        return min([ g.precision() for g in self.__gen_expansions + self.__base_gen_expansions])
    
    @cached_method
    def fourier_ring(self) :
        """
        The ring that Fourier expansions of all elements of this
        ring will be contained in.
        
        OUTPUT:
            An ambient of (equivariant) monoid power series.
        
        TESTS::
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_basicmonoids import *
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_ring import *
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_element import *
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_grading import DegreeGrading
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_ring import *
            sage: mps = MonoidPowerSeriesRing(ZZ, NNMonoid(False))
            sage: ger = GradedExpansionRing_class(None, Sequence([mps(1)]), PolynomialRing(QQ, 'a').ideal(0), DegreeGrading((1,)))
            sage: ger.fourier_ring()
            Ring of monoid power series over NN
            sage: ger = GradedExpansionRing_class(Sequence([MonoidPowerSeries(mps, {1 : 1}, mps.monoid().filter(2))]), Sequence([MonoidPowerSeries(mps, {1 : 1, 2 : 3}, mps.monoid().filter(4))]), PolynomialRing(ZZ, ['a', 'b']).ideal(0), DegreeGrading((1,2)))
            sage: ger.fourier_ring()
            Ring of monoid power series over NN
        """
        if self.__gen_expansions.universe().base_ring() == self.base_ring() :
            return self.__gen_expansions.universe()
        else :
            from sage.categories.pushout import pushout
            
            if self.nbasegens() == 0 :
                scalar_ring = self.base_ring()
            else :
                scalar_ring = self.base_ring().base_ring()
            
            return pushout(self.__gen_expansions.universe(), scalar_ring) 
    
    #===========================================================================
    # def precision(self) :
    #    """
    #    Return the minimal precision of any fourier expansion in this ring.
    #    """
    #    return min([g.precision() for g in self._generator_expansions()])
    #===========================================================================

    def _set_evaluation_hom(self, hom) :
        """
        Set the homomorphism that maps every polynomial in the underlying
        polynomial ring to its expansion.
        
        INPUT:
            - ``hom`` -- A morphism with domain a polynomial ring and
                         domain an ambient of (equivariant) monoid power series.
        
        OUTPUT:
            ``None``.
        
        TESTS::
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_basicmonoids import *
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_ring import *
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_element import *
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_grading import DegreeGrading
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_ring import *
            sage: mps = MonoidPowerSeriesRing(QQ, NNMonoid(False))
            sage: ger = GradedExpansionRing_class(None, Sequence([mps(1)]), PolynomialRing(ZZ, 'a').ideal(0), DegreeGrading((1,)))
            sage: ger2 = GradedExpansionRing_class(None, Sequence([mps(2)]), PolynomialRing(ZZ, 'a').ideal(0), DegreeGrading((1,)))
            sage: ger2._set_evaluation_hom(ger._GradedExpansionAmbient_abstract__evaluation_hom)
            sage: ger2.0.fourier_expansion().coefficients()
            {0: 1}
        """
        self.__evaluation_hom = hom
    
    def _fourier_expansion_of_element(self, e) :
        """
        The Fourier expansion of an element `e`.
        
        INPUT:
            - `e` -- An element of the ``self``.
        
        OUTPUT:
            A (equivariant) monoid power series.
        
        SEE:
            :class:~`.fourier_expansion_framework.gradedexpansions.fourierexpansionwrapper.FourierExpansionWrapper`.
        
        TESTS::
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_basicmonoids import *
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_ring import *
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_element import *
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_grading import DegreeGrading
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_ring import *
            sage: mps = MonoidPowerSeriesRing(QQ, NNMonoid(False))
            sage: ger = GradedExpansionRing_class(Sequence([MonoidPowerSeries(mps, {1 : 1}, mps.monoid().filter(2))]), Sequence([MonoidPowerSeries(mps, {1 : 1, 2 : 3}, mps.monoid().filter(4))]), PolynomialRing(QQ, ['a', 'b']).ideal(0), DegreeGrading((1,2)))
            sage: ger.0.fourier_expansion() # indirect doctest
            Monoid power series in Ring of monoid power series over NN
            sage: (ger.basegens()[0]^2 * 2*ger.0).fourier_expansion() # indirect doctest
            Monoid power series in Ring of monoid power series over NN
            sage: (ger.basegens()[0] + 5*ger.0).fourier_expansion() # indirect doctest
            Monoid power series in Ring of monoid power series over NN
        """
        return self.__evaluation_hom(e.polynomial())
    
#===============================================================================
#    def graded_submodules_are_free(self) :
#        """
#        If ``True`` is returned, there are no relations within the module
#        formed by the Fourier expansions - thought of as expansions with
#        infinite precision - for a fixed grading value.
# 
#        OUTPUT:
#            A boolean.
#        
#        TESTS::
#            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_basicmonoids import *
#            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_ring import *
#            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_element import *
#            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_grading import DegreeGrading
#            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_ring import *
#            sage: mps = MonoidPowerSeriesRing(QQ, NNMonoid(False))
#            sage: ger = GradedExpansionRing_class(None, Sequence([mps(1)]), PolynomialRing(ZZ, 'a').ideal(0), DegreeGrading((1,)))
#            sage: ger.graded_submodules_are_free()
#            False
#        """
#        return False
#===============================================================================

    def _graded_monoms(self, index) :
        """
        Return all monoms in the generators that have a given grading index.
        
        INPUT:
            - ``index`` -- A grading values.
        
        OUTPUT:
            A list of elements of ``self``.
        
        TESTS::
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_basicmonoids import *
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_ring import *
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_element import *
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_grading import DegreeGrading
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_ring import *
            sage: mps = MonoidPowerSeriesRing(QQ, NNMonoid(False))
            sage: ger = GradedExpansionRing_class(None, Sequence([MonoidPowerSeries(mps, {1 : 4, 2 : 3}, mps.monoid().filter(4)), MonoidPowerSeries(mps, {1 : 1, 2 : 3}, mps.monoid().filter(4))]), PolynomialRing(ZZ, ['a', 'b']).ideal(0), DegreeGrading((1,2)))
            sage: GradedExpansionAmbient_abstract._graded_monoms(ger, 3)
            Traceback (most recent call last):
            ...
            NotImplementedError
        """        
        raise NotImplementedError

    def graded_submodule(self, indices, **kwds) :
        """
        The submodule which contains all elements of given 
        grading values.
        
        INPUT:
            - ``indices`` -- A list or tuple of grading values or a single grading value.
            - ``**kwds``  -- A dictionary of keywords; They will be passed to the
                             submodule constructor.
        
        OUTPUT:
            An instance of :class:~`fourier_expansion_framework.gradedexpansions.gradedexpansion_submodule.GradedExpansionSubmodule_abstract`.

        TESTS::
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_basicmonoids import *
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_ring import *
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_module import *
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_element import *
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_grading import DegreeGrading
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_ring import *
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_module import *
            sage: mps = MonoidPowerSeriesRing(QQ, NNMonoid(False))
            sage: ger = GradedExpansionRing_class(None, Sequence([MonoidPowerSeries(mps, {1 : 4, 2 : 3}, mps.monoid().filter(4)), MonoidPowerSeries(mps, {1 : 1, 2 : 3}, mps.monoid().filter(4))]), PolynomialRing(ZZ, ['a', 'b']).ideal(0), DegreeGrading((1,2)))
            sage: sm = ger.graded_submodule(2)
            sage: ger = GradedExpansionRing_class(None, Sequence([MonoidPowerSeries(mps, {1 : 4, 2 : 3}, mps.monoid().filter_all()), MonoidPowerSeries(mps, {1 : 1, 2 : 3}, mps.monoid().filter_all())]), PolynomialRing(ZZ, ['a', 'b']).ideal(0), DegreeGrading((1,2)))
            sage: sm = ger.graded_submodule(3)
            sage: P.<a,b,c> = PolynomialRing(QQ)
            sage: ger = GradedExpansionRing_class(None, Sequence([MonoidPowerSeries(mps, {1 : 4, 2 : 3}, mps.monoid().filter_all()), MonoidPowerSeries(mps, {1 : 1, 2 : 3}, mps.monoid().filter_all()), MonoidPowerSeries(mps, {2 : 1, 3: 6, 4 : 9}, mps.monoid().filter_all())]), P.ideal(b^2 - c), DegreeGrading((1,2)))
            sage: sm = ger.graded_submodule(4)
            sage: m = FreeModule(QQ, 3)
            sage: mpsm = MonoidPowerSeriesModule(m, NNMonoid(False))
            sage: mps = mpsm.base_ring()
            sage: ger = GradedExpansionModule_class(None, Sequence([MonoidPowerSeries(mpsm, {1 : m([1,2,3]), 2 : m([3,-3,2])}, mpsm.monoid().filter(4)), MonoidPowerSeries(mpsm, {1 : m([2,-1,-1]), 2 : m([1,0,0])}, mpsm.monoid().filter(4))]), PolynomialRing(ZZ, ['a', 'b']).ideal(0), DegreeGrading((1,2)))
            sage: ger.graded_submodule(4).rank()
            0
        """
        #=======================================================================
        # if not self.graded_submodules_are_free() :
        #    raise ValueError( "Graded submodules of must be free." )
        #=======================================================================
        
        if indices in self.grading() :
            indices = tuple([indices])
        elif isinstance(indices, list) :
            indices = tuple(indices)
        elif not isinstance(indices, tuple) :
            raise TypeError( "Wrong type of indices." )
            
        try :
            return self.__graded_submodules[indices]
        except KeyError :
            pass

        module_gens = flatten(map(self._graded_monoms, indices), max_level = 1)        
        
        if self.has_relation_free_generators() :
            basis = module_gens
        else :
            module_gens_poly = map(lambda g: g.polynomial(), module_gens) 
            basis = list()
            
            I = self.relations().ring().zero_ideal()
            for i,g in enumerate(module_gens_poly) :
                rg = I.reduce(g)
                
                if not rg.is_zero() :
                    I = I.ring().ideal([rg] + list(I.gens_reduced()))
                    basis.append(module_gens[i])

        self.__graded_submodules[indices] = self._submodule(basis, grading_indices = indices, **kwds)
        
        return self.__graded_submodules[indices] 
    
    def _submodule(self, arg, *args, **kwds) :
        """
        Return a submodule of ``self``.
        
        INPUT:
            - `arg` -- A list of elements of ``self``.
        
        OUTPUT:
            An instance of :class:~`fourier_expansion_framework.gradedexpansions.gradedexpansion_submodule.GradedExpansionSubmodule_abstract`.
        
        TESTS::
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_basicmonoids import *
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_ring import *
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_element import *
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_grading import DegreeGrading
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_ring import *
            sage: mps = MonoidPowerSeriesRing(QQ, NNMonoid(False))
            sage: ger = GradedExpansionRing_class(None, Sequence([MonoidPowerSeries(mps, {1 : 4, 2 : 3}, mps.monoid().filter(4)), MonoidPowerSeries(mps, {1 : 1, 2 : 3}, mps.monoid().filter(4))]), PolynomialRing(ZZ, ['a', 'b']).ideal(0), DegreeGrading((1,2)))
            sage: sm = ger.graded_submodule(2) # indirect doctest
        """
        if isinstance(arg, list) :
            return GradedExpansionSubmodule(self, arg)
        else :
            raise NotImplementedError

    def __cmp__(self, other) :
        """
        TESTS::
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_basicmonoids import *
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_ring import *
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_element import *
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_grading import DegreeGrading
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_ring import *
            sage: mps = MonoidPowerSeriesRing(QQ, NNMonoid(False))
            sage: ger = GradedExpansionRing_class(None, Sequence([MonoidPowerSeries(mps, {1 : 4, 2 : 3}, mps.monoid().filter(4)), MonoidPowerSeries(mps, {1 : 1, 2 : 3}, mps.monoid().filter(4))]), PolynomialRing(QQ, ['a', 'b']).ideal(0), DegreeGrading((1,2)))
            sage: ger == GradedExpansionRing_class(None, Sequence([MonoidPowerSeries(mps, {1 : 4, 2 : 3}, mps.monoid().filter(4)), MonoidPowerSeries(mps, {1 : 1, 2 : 3}, mps.monoid().filter(4))]), PolynomialRing(QQ, ['a', 'b']).ideal(0), DegreeGrading((1,2)))
            True
            sage: ger == GradedExpansionRing_class(None, Sequence([MonoidPowerSeries(mps, {1 : 4, 2 : 3}, mps.monoid().filter(4)), MonoidPowerSeries(mps, {1 : 1, 2 : 3}, mps.monoid().filter(4))]), PolynomialRing(QQ, ['a', 'b']).ideal(0), DegreeGrading((1,3)))
            False
            sage: P.<a,b> = PolynomialRing(QQ)
            sage: ger == GradedExpansionRing_class(None, Sequence([MonoidPowerSeries(mps, {1 : 4, 2 : 3}, mps.monoid().filter(4)), MonoidPowerSeries(mps, {1 : 1, 2 : 3}, mps.monoid().filter(4))]), P.ideal(a^2 - b), DegreeGrading((1,2)))
            False
            sage: ger == GradedExpansionRing_class(None, Sequence([MonoidPowerSeries(mps, {1 : 4, 2 : 3}, mps.monoid().filter(4)), MonoidPowerSeries(mps, {1 : 1, 2 : 4}, mps.monoid().filter(4))]), PolynomialRing(QQ, ['a', 'b']).ideal(0), DegreeGrading((1,2)))
            False
            sage: ger == GradedExpansionRing_class(Sequence([MonoidPowerSeries(mps, {1 : 4}, mps.monoid().filter(4))]), Sequence([MonoidPowerSeries(mps, {1 : 4, 2 : 3}, mps.monoid().filter(4)), MonoidPowerSeries(mps, {1 : 1, 2 : 3}, mps.monoid().filter(4))]), PolynomialRing(QQ, ['a', 'b', 'c']).ideal(0), DegreeGrading((1,2,2)))
            False
        """
        c = cmp(type(self), type(other))
        if c == 0 :
            c = cmp(self.__relations, other.__relations)
        if c == 0 :
            c = cmp(self.__all_relations, other.__all_relations)
        if c == 0 :
            c = cmp(self.__grading, other.__grading)
        if c == 0 :
            c = cmp(self.__base_gen_expansions, other.__base_gen_expansions)
        if c == 0 :
            c = cmp(self.__gen_expansions, other.__gen_expansions)
            
        return c
    
    def construction(self) :
        """
        TESTS::
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_basicmonoids import *
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_ring import *
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_element import *
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_grading import DegreeGrading
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_ring import *
            sage: mps = MonoidPowerSeriesRing(QQ, NNMonoid(False))
            sage: ger = GradedExpansionRing_class(None, Sequence([MonoidPowerSeries(mps, {1 : 4, 2 : 3}, mps.monoid().filter(4)), MonoidPowerSeries(mps, {1 : 1, 2 : 3}, mps.monoid().filter(4))]), PolynomialRing(QQ, ['a', 'b']).ideal(0), DegreeGrading((1,2)))
            sage: (F, A) = ger.construction()
            sage: ger == F(A)
            True
        """
        return ( GradedExpansionFunctor(self.__base_gen_expansions, self.__gen_expansions,
                                        self.__relations, self.__grading, self.__all_relations ), \
                 self.base_ring() )

    def _element_constructor_(self, x) :
        """
        INPUT:
            - `x` -- An element of the underlying polynomial ring or
                     an element in a submodule of graded expansions.
        
        OUTPUT:
            An instance of the element class.
        
        TESTS::
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_basicmonoids import *
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_module import *
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_element import *
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_grading import DegreeGrading
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_ring import *
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_module import *
            sage: mps = MonoidPowerSeriesRing(QQ, NNMonoid(False))
            sage: ger = GradedExpansionRing_class(Sequence([MonoidPowerSeries(mps, {1: 1}, mps.monoid().filter(4))]), Sequence([MonoidPowerSeries(mps, {1: 1, 2: 3}, mps.monoid().filter(4))]), PolynomialRing(QQ, ['a', 'b']).ideal(0), DegreeGrading((1,2)))
            sage: h = ger(PolynomialRing(QQ, ['a', 'b']).gen(0))
            sage: sm = ger.graded_submodule(3)
            sage: h = ger(sm.0)
            sage: m = FreeModule(QQ, 3)
            sage: mpsm = MonoidPowerSeriesModule(m, NNMonoid(False))
            sage: mps = mpsm.base_ring()
            sage: ger = GradedExpansionModule_class(Sequence([MonoidPowerSeries(mps, {1: 1}, mps.monoid().filter(4))]), Sequence([MonoidPowerSeries(mpsm, {1: m([1,1,1]), 2: m([1,3,-3])}, mpsm.monoid().filter(4))]), PolynomialRing(QQ, ['a', 'b']).ideal(0), DegreeGrading((1,2)))
            sage: h = ger(PolynomialRing(QQ, ['a', 'b']).gen(1))
            sage: sm = ger.graded_submodule(3)
            sage: h = ger(sm.0)
        """
        if isinstance(x, Element) :
            P = x.parent()
            if P is self.relations().ring() :
                return self._element_class(self, x)
            elif isinstance(P, GradedExpansionSubmodule_abstract) :
                if self is P.graded_ambient() :
                    return P._graded_expansion_submodule_to_graded_ambient_(x)                
                elif self.has_coerce_map_from(P.graded_ambient()) :
                    return self(P.graded_ambient()(x))
            ## We cannot handle base extensions here, because we don't know anything
            ## about additional relations which may occur. So deriving classes have
            ## to care about this.
                   
        raise TypeError( "The element %s cannot be converted into %s," % (x, self) )

    def __hash__(self) :
        """
        TESTS::
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_basicmonoids import *
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_ring import *
            sage: from psage.modform.fourier_expansion_framework.monoidpowerseries.monoidpowerseries_element import *
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_grading import DegreeGrading
            sage: from psage.modform.fourier_expansion_framework.gradedexpansions.gradedexpansion_ring import *
            sage: mps = MonoidPowerSeriesRing(QQ, NNMonoid(False))
            sage: ger = GradedExpansionRing_class(None, Sequence([MonoidPowerSeries(mps, {1 : 4, 2 : 3}, mps.monoid().filter(4)), MonoidPowerSeries(mps, {1 : 1, 2 : 3}, mps.monoid().filter(4))]), PolynomialRing(QQ, ['a', 'b']).ideal(0), DegreeGrading((1,2)))
            sage: hash(ger)
            921050467 # 32-bit
            3906772531912514915 # 64-bit
        """
        return reduce(xor, map(hash, [self.__grading, self.__relations,
                                      self.__all_relations, self.__base_gens, self.__gens]) )
